package 分类.二叉搜索树;

public class 删除二叉搜索树中的节点 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        if(root.val==key){
            if(root.left==null) return root.right;
            if(root.right==null) return root.left;
            //获取右子树的最小节点
            TreeNode right=root.right;
            TreeNode min=getMin(right);
            root.right=deleteNode(root.right,min.val);
            min.left=root.left;
            min.right=root.right;
            root=min;
        }else {
            if(root.val< key){
                root.right=deleteNode(root.right,key);
            }else{
                root.left=deleteNode(root.left,key);
            }
        }
        return root;
    }
    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) node = node.left;
        return node;
    }
}
